#include<bits/stdc++.h>
using namespace std;
using ll=long long;
using li=__int128;
using pi=pair<int,int>;
#define fi first
#define se second
const int N=2005;
int n,m,sx,tx,type,d[N],f[N][N];
pi w[N],e[N];
void bfs(int s) {
    for(int i=1;i<=n;i++)d[i]=-1;
    queue<int>q;q.push(s),d[s]=0;
    while(q.size()) {
        int x=q.front();q.pop();
        // for(int y:e[x])if(d[y]==-1)d[y]=d[x]+1,q.push(y);
    }
}
void solve() {
    cin>>n>>m;
    for(int i=1,x,y;i<=m;i++)cin>>x>>y,w[i]={x,y};
    if(n<=7) {
        int tot=0,mn=-1e9,as=0;
        for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)e[tot++]={i,j};
        for(int i=0;i<1<<tot;i++)if(__builtin_popcount(i)==m-1) {
            for(int j=1;j<=n;j++)for(int k=1;k<=n;k++)if(j!=k)f[j][k]=1e9;
            for(int j=0;j<tot;j++)if(i>>j&1)f[e[j].fi][e[j].se]=f[e[j].se][e[j].fi]=1;
            for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++) 
                f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
            int s=0;
            for(int j=1;j<=m;j++) {
                if(f[w[j].fi][w[j].se]>=1e8){s=-1e9;break;}
                s-=f[w[j].fi][w[j].se];
            }
            if(s>mn)mn=s,as=1;else as+=(mn==s);
        }
        cout<<mn<<' '<<as<<'\n';
    }else {
        cout<<-2*m+2<<" 0\n";
    }
}
int main() {
    freopen("oi.in","r",stdin);
    freopen("oi.out","w",stdout);
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int tt;cin>>type>>tt;
    while(tt--)solve();
    return 0;
}